package lcof;


import java.util.Deque;
import java.util.LinkedList;

/**
 * @author 江岸
 * @version V1.0
 * @ClassName: VerifyPostorder33
 * @description: 输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 true，否则返回 false。假设输入的数组的任意两个数字都互不相同。
 * @date 2021/5/1016:26
 * @since V1.0
 */
public class VerifyPostorder33 {
    //单调栈
    public boolean verifyPostorder(int[] postorder) {
        // 单调栈使用，单调递增的单调栈
        Deque<Integer> stack = new LinkedList<>();
        int pervElem = Integer.MAX_VALUE;
        // 逆向遍历，就是翻转的先序遍历
        for (int i = postorder.length - 1;i>=0;i--){
            // 左子树元素必须要小于递增栈被peek访问的元素，否则就不是二叉搜索树
            if (postorder[i] > pervElem){
                return false;
            }
            while (!stack.isEmpty() && postorder[i] < stack.peek()){
                // 数组元素小于单调栈的元素了，表示往左子树走了，记录下上个根节点
                // 找到这个左子树对应的根节点，之前右子树全部弹出，不再记录，因为不可能在往根节点的右子树走了
                pervElem = stack.pop();
            }
            // 这个新元素入栈
            stack.push(postorder[i]);
        }
        return true;
    }



    //递归
    public boolean fun(int[] postorder ,int left,int right){
        if (left>=right){
            //传入的子树只有一个元素,或者没有元素[]。返回true
            return true;
        }
        int m = left;
        int root = postorder[right];
        //找到左子树范围[left,m-1];
        while (postorder[m]<root) m++;
        //右子树范围[m,right-1],进行校验
        for (int i=m;i<right;i++){
            //确保右子树中每个元素都大于root
            if (postorder[i]<root) return false;
        }
        return fun(postorder,left,m-1)&&fun(postorder,m,right-1);

    }

    public static void main(String[] args) {
//        verifyPostorder(new int[]{1,3,6,5,2});
    }
}
